package leetcode.editor.cn;

//给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
//
// 测试用例的答案是一个 32-位 整数。
//
//
//
// 示例 1:
//
//
//输入: nums = [2,3,-2,4]
//输出: 6
//解释: 子数组 [2,3] 有最大乘积 6。
//
//
// 示例 2:
//
//
//输入: nums = [-2,0,-1]
//输出: 0
//解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
//
//
//
// 提示:
//
//
// 1 <= nums.length <= 2 * 10⁴
// -10 <= nums[i] <= 10
// nums 的任何前缀或后缀的乘积都 保证 是一个 32-位 整数
//
//
// Related Topics 数组 动态规划 👍 2286 👎 0

import java.util.Arrays;

public class MaximumProductSubarray {
    public static void main(String[] args) {
        Solution solution = new MaximumProductSubarray().new Solution();

        System.out.println(solution.maxProduct(new int[]{-2,3,-4}));

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 定义一个二维数组dp[i][2]   i表示以i结尾的最大乘积和最小乘积 dp[i][0] 表示最大乘机 dp[i][1]表示最小乘机
         * 不能只保存最大乘积，因为 负数乘积有可能变成正数
         * @param nums
         * @return
         */
        public int maxProduct(int[] nums) {

            int[][] dp = new int[nums.length][2];
            dp[0][0] = nums[0];
            dp[0][1] = nums[0];
            int max = dp[0][0];
            for (int i = 1; i < nums.length; i++) {
                if (nums[i] == 0) {
                    dp[i][0] = 0;
                    dp[i][1] = 0;
                }
                else if (nums[i] > 0) {
                    //最大值
                    if (dp[i - 1][0] > 0) {
                        dp[i][0] = nums[i] * dp[i - 1][0];
                    }
                    if (dp[i - 1][0] <= 0) {
                        dp[i][0] = nums[i];
                    }
                    //最小值
                    if (dp[i - 1][1] > 0) {
                        dp[i][1] = nums[i];
                    }
                    if (dp[i - 1][1] <= 0) {
                        dp[i][1] = nums[i] * dp[i - 1][1];
                    }

                } else if (nums[i] < 0) {

                    //最小值,如果dp[n-1]
                    if (dp[i - 1][0] > 0) {
                        dp[i][1] = nums[i] * dp[i - 1][0];
                    }
                    if (dp[i - 1][0] <= 0) {
                        dp[i][1] = nums[i];
                    }
                    //最大值
                    if (dp[i - 1][1] == 0) {
                        dp[i][0] =  dp[i - 1][1];
                    }
                    if (dp[i - 1][1] > 0) {
                        dp[i][0] = nums[i] ;
                    }
                    if (dp[i - 1][1] < 0) {
                        dp[i][0] = nums[i] * dp[i - 1][1];
                    }

                }
                max = Math.max(max, dp[i][0]);
            }
            for (int i = 0; i < dp.length; i++){
                System.out.println(Arrays.toString(dp[i]));
            }
            return max;

        }
        public int maxProduct2(int[] nums) {

            int[] dp= new int[nums.length];
            dp[0] = nums[0];
            int max = dp[0];
            for (int i = 1; i < nums.length; i++){
                if (nums[i] > 0){
                    if (dp[i-1] > 0){
                        dp[i] = nums[i] * dp[i-1];
                    }
                    if (dp[i-1] <= 0)
                        dp[i] = nums[i];

                }else if (nums[i] < 0){
                    if (dp[i-1] > 0){
                        dp[i] = nums[i]  ;
                    }
                    if (dp[i-1] <= 0)
                        dp[i] = nums[i] * dp[i-1];

                }else if (nums[i] == 0){
                    dp[i] = 0;
                }
                max = Math.max(max, dp[i]);
            }
            return max;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
